package com.zjj.lbw.algorithm.sort;

import java.util.Arrays;

/**
 * @author zhanglei.zjj
 * @description 堆排序
 * @date 2023/4/1 14:52
 */
public class HeadSort {
    public static void main(String[] args) {
        int[] unsortedArr = new int[]{35, 63, 48, 9, 86, 24, 53, 11};
        System.out.println("排序前元素顺序为：" + Arrays.toString(unsortedArr));

        // 构建二叉堆
        buildBinaryHeap(unsortedArr);

        // 开始堆排序
        heapSort(unsortedArr);

    }

    private static void heapSort(int[] arr) {
        int sortedCount = 0;
        while (sortedCount < arr.length -1) {
            // 将第一个元素和最后一个元素交换
            int temp = arr[0];
            int willSortingIndex = arr.length - 1 - sortedCount;
            arr[0] = arr[willSortingIndex];
            arr[willSortingIndex] = temp;

            // 后续只用调整尚未交换到堆尾的元素
            int arrLen = arr.length - (++ sortedCount);
            compareAndSwap(arr, arrLen, 0);
        }

        System.out.println("降序排序后元素顺序为：" + Arrays.toString(arr));
    }

    private static void buildBinaryHeap(int[] arr) {
        int len = arr.length;
        int curNode = len / 2 - 1;
        while (curNode >= 0) {
            compareAndSwap(arr, len, curNode);
            curNode --;
        }
    }

    private static void compareAndSwap(int[] arr, int len, int curNode) {
        int curMinIndex = curNode;
        int left = 2 * curNode + 1;
        int right = 2 * (curNode + 1);

        if (left < len && arr[left] < arr[curNode]) {
            curMinIndex = left;
        }
        if (right < len && arr[right] < arr[curMinIndex]) {
            curMinIndex = right;
        }

        if (curMinIndex != curNode) {
            int temp = arr[curNode];
            arr[curNode] = arr[curMinIndex];
            arr[curMinIndex] = temp;

            // 交换后，可能对子树有影响
            compareAndSwap(arr, len, curMinIndex);
        }
    }
}

